#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

/**
 * Definition for binary tree */
struct TreeNode {
   int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	bool isBalanced(TreeNode *root) {
		if(root==NULL)
			return true;
		int BF=abs(height(root->left)-height(root->right));
		return isBalanced(root->left)&&isBalanced(root->right)&&BF<=1;
	}

	//calculate height of tree
	int height(TreeNode *root){
		if(root==NULL)
			return 0;
		return 1+max(height(root->left),height(root->right));
	}

	//return the bigger value of two number
	int max(int a,int b){
		if(a>=b)
			return a;
		else
			return b;
	}
};

int main(){
	TreeNode root(2);
	TreeNode node_1(1);
	TreeNode node_2(1);
	TreeNode node_3(1);
	TreeNode node_4(1);

	root.left=&node_1;
	root.right=&node_2;
	node_1.left=&node_3;
	node_3.left=&node_4;
	
	Solution solution;
	cout<<solution.isBalanced(&root)<<endl;
}
